\documentclass[utf8]{ctexart}

\usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{booktabs}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{indentfirst}
\usepackage{gnuplot-lua-tikz}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{shapes.geometric, arrows}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{newclude}
\usepackage[perpage]{footmisc}

\graphicspath{ {../images/} }
\raggedbottom	% 令页面在垂直方向向顶部对齐
\renewcommand\qedsymbol{QED}
\newcommand{\sign}[1]{\mathrm{sgn}(#1)}
\everymath{\displaystyle}   % 行内公式采用行间公式格式排列

\title{第二次上机作业报告}
\author{姓名：殷文良\qquad 学号：3200101893}
\date{}

\begin{document}
\maketitle
\CTEXsetup[format={\Large\bfseries}]{section}

\section{项目设计思路}
\begin{enumerate}
\item
  BinarySearchTree类的构建使用教材上的源代码，另外补充了前序、中序和后序遍历二叉搜索树的操作。
\item
  打乱操作采用 STL标准库中<algorithm>头文件里的\verb!shuffle!函数；利用二叉树进行数据的插入之后，中序遍历输出即为从小到大的顺序。
\item
  分别测试了不打乱和打乱情况下排序算法的平均效率，以及不打乱情况下的最坏效率。
\end{enumerate}


\section{测试说明}
\begin{itemize}
\item
  在shell终端输入\verb!make report!，可以得到上机报告report.pdf；
\item
  在shell终端输入\verb!make(compile)!，可以编译C++程序main.cpp，输入\verb!./test!可在终端得到输出结果；
\item
  在shell终端输入\verb!bash run number!（number为随机生成在$-50000\sim 50000$的整数数目，缺省值为10），可以将输出结果重定向到文件result.txt中；
\item
  在shell终端输入\verb!make check!，可以检查程序main.cpp的内存泄漏情况。
\end{itemize}

\section{测试结果}
\subsection{程序运行结果}
图\ref{fig1}显示了数组大小为10的数组在排序前后的结果，验证了排序算法的正确性。
\begin{figure}[H]
  \centering
  \includegraphics[width=0.771\textwidth,height=0.410\textwidth]{2_1.png}
  \caption{程序运行结果}
  \label{fig1}
\end{figure}

\subsection{内存泄露检查}
图\ref{fig2}说明程序不存在内存泄露的情况。
\begin{figure}[H]
  \centering
  \includegraphics[width=0.789\textwidth,height=0.742\textwidth]{2_2.png}
  \caption{内存泄漏检查}
  \label{fig2}
\end{figure}

\subsection{效率分析}
\begin{enumerate}
\item
  不同大小数组的测试运行时间（单位：s）如表\ref{tab1}所示。
  \begin{table}[H]
    \centering
    \begin{tabular}{cccc}
      \toprule
      size & mode\_0\_avg & mode\_1\_avg & mode\_0\_worst\\
      \midrule
      10   &    0.000005 &   0.000005 &     0.000002\\
      50   &    0.000011 &   0.000013 &     0.000021\\
      100  &    0.000021  &  0.000025    &  0.000059\\
      1000  &   0.000545  & 0.000664    &  0.007762\\
      10000 &   0.003658  &  0.004353    &  0.683889\\
      20000 &   0.010901  &  0.009385    &  2.984680\\
      50000 &   0.023839  &  0.019132    & 15.582900\\
      \bottomrule
    \end{tabular}
    \caption{运行时间}
    \label{tab1}
  \end{table}\par
  由于随机二叉树排序还需要额外的 shuffle 打乱，所以当数据没有明显的顺序性时时间消耗会比普通二叉树排序多一些，但是随机二叉树排序考虑到了树的深度，当我们考虑一串整齐的数列，例如$1,2,3,\cdots$，这会使得普通的插入形成了很深的树不利于树的搜索排序。图\ref{fig3}比较了不同情况下排序算法的效率，可以看到当数据量很大且为有序数列时，普通的BST\_Sort明显慢于随机的BST\_sort。
\begin{figure}[H]
  \centering
  \includegraphics[width=0.566\textwidth,height=0.457\textwidth]{2_3.png}
  \caption{不同算法的效率比较}
  \label{fig3}
\end{figure}
  
\item
  由图\ref{fig4}可以看到，普通BST\_Sort算法和随机BST\_Sort算法在随机排序的数组上的运行时间在一个数量级上且相差很小，说明二者的平均效率相近。
  \begin{figure}[H]
  \centering
  \includegraphics[width=0.570\textwidth,height=0.457\textwidth]{2_4.png}
  \caption{普通BST\_Sort算法与随机BST\_Sort算法的平均效率比较}
  \label{fig4}
  \end{figure}
\item
  由理论分析可以得到，普通BST\_Sort算法与随机BST\_Sort算法的平均复杂度均为$O(n\log{n})$，而普通BST\_Sort算法的最坏复杂度为$O(n^2)$。图\ref{fig5}通过函数拟合，验证了这一结论的正确性。
  \begin{figure}[H]
  \centering
  \includegraphics[width=1.000\textwidth,height=0.320\textwidth]{2_5.png}
  \caption{复杂度分析}
  \label{fig5}
  \end{figure}
\end{enumerate}

\end{document}
